/*
 * @lc app=leetcode.cn id=1254 lang=cpp
 *
 * [1254] 统计封闭岛屿的数目
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        rowNum_ = grid.size();
        colNum_ = grid[0].size();

        // set all margin cells sea (0 => 1)
        for (int col=0;col<colNum_;++col) {
            DFSCluster(grid, 0, col, 1);
        }
        for (int col=0;col<colNum_;++col) {
            DFSCluster(grid, rowNum_-1, col, 1);
        }
        for (int row=1;row<rowNum_-1;++row) {
            DFSCluster(grid, row, 0, 1);
        }
        for (int row=1;row<rowNum_-1;++row) {
            DFSCluster(grid, row, colNum_-1, 1);
        }

        ShowGrid(grid);

        // start cluster ~
        for (int row=1;row<rowNum_-1;++row) {
            for (int col=1;col<colNum_-1;++col) {
                if (grid[row][col] == 0) {
                    clusterCounter_ += 1;
                    // printf("new cluster %d at %d %d\n", clusterCounter_, row, col);
                    DFSCluster(grid, row, col, clusterCounter_);
                }
            }
        }

        ShowGrid(grid);

        return clusterCounter_;
    }
private:
    int rowNum_, colNum_;
    int clusterCounter_ = 0;
    // std::map<int, std::pair<int, int>> recordLeftTopCell_;
private:
    void DFSCluster(vector<vector<int>>& grid, int row, int col, int clusterId) {
        // check inside map
        if (row < 0 or row >= rowNum_ or col < 0 or col >= colNum_) return;
        // check sea or visited
        if (grid[row][col] != 0) return;
        // start dfs
        grid[row][col] = clusterId;
        for (int direction=0;direction<4;++direction) {
            DFSCluster(grid, row+directions[direction][0], col+directions[direction][1], clusterId);
        }
    }
    // each cluster start with top left cell
    // inject direction = right
    void mooreTracing() {
        ;
    }

    void ShowGrid(vector<vector<int>>& grid) {
        // printf("--------------------\n");
        // for (int row=0;row<rowNum_;++row) {
        //     for (int col=0;col<colNum_;++col) {
        //         printf(" %d", grid[row][col]);
        //     }
        //     printf("\n");
        // }
    }
private:
    const int directions[4][2] = {
        // row, col
        { 0,  1}, // right
        { 1,  0}, // down
        { 0, -1}, // left
        {-1,  0}, // top
    };
};
// @lc code=end

